package nan.recursionshuzu;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    /*
    二维数组打印
     */
    public static void main56(String[] args) {
        //二维数组的每一个元素又是一个一维数组
        int[][] array={{1,2,3},{4,5,6}};//定义一个二维数组为两行三列
        System.out.println(array[1][2]);//打印array[1][2]
        for(int i=0;i<array.length;i++){//外层for循环控制行数，数组的长度就为行数
            for(int j=0;j<array[i].length;j++){//内层for循环控制列，第i行数组的长度，
                // 表示列
                System.out.print(array[i][j]+" ");
            }
            System.out.println();
        }
    }
    /*
    冒泡排序:例如总共五个数据，比较了四趟：所以定义i表示趟数;再使用for循环，
    j代表每次下标之间的比较
    定义j是第一趟从数组0号开始，循环四次，到array.length-1-i号结束，
    因为每趟都比上一次少一趟
    注：每趟结束需要比较此时是否已经为一个有序数列
     */
    public static void bubbleSort(int[] array){
        boolean flag=false;//定义一个布尔类型的变量flag，作为判断每趟结束
        // 之后是否已经是有序序列
        for(int i=0;i< array.length-1;i++){//定义趟数，
            // 趟数为array.length-1
            for(int j=0;j< array.length-1-i;j++){//定义每次下标之间的比
                // 较，每次数组下标之间的比较次数都要比上一次少一趟，
                // 要是array[j]>array[j+1]，就交换数据
                flag=false;//每一趟都要将flag置位false
                if(array[j]>array[j+1]){
                    int tmp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=tmp;//交换数据
                    flag=true;//如果发生交换，就把flag置位true；
                }
            }
            if(flag==false){//说明在这趟比较中没有进入if交换
                break;
            }
        }
    }
    public static void main18(String[] args) {
        int[] array={2,1,3,4,5};
        bubbleSort(array);
        System.out.println(Arrays.toString(array));
    }
    /*
    判断数组是否是递增
     */
    public static boolean isSored(int[] array){
        if(array==null||array.length==0){//如果array是空引用或者array长度为0
            // 就返回false
            return false;
        }
        for(int i=0;i< array.length-1;i++){//遍历数组，注意此时for循环中
            // 判断条件应改为length-1，因为你在if中要用array[i+1]做判断
            if (array[i] < array[i+1]) {//如果array[i] < array[i+1]，则说明
                // 数组前一项比后一项小，数组为递增，返回true，因为返回值为boolean类型
                return true;
            }
        }
        return false;
    }
    public static void main17(String[] args) {
        int[] array={0,0,0,0};//定义数组
        System.out.println(isSored(array));//调用并接收
    }
    /*
    二分查找
     */
    public static int binarySearch(int[] array3,int key) {
        int left = array3[0];//定义left为数组中第一个数
        int right = array3.length - 1;//定义right为数组中的最后一个数
        while (left <= right) {//当left<right的时候
            int mid = (left + right) / 2;//每次mid都为(left + right) / 2
            if (array3[mid] > key) {//如果mid值大于key，说明key在左边，
                // 所以将right移到mid-1的位置
                right=mid-1;
            }else if (array3[mid]<key){//如果mid的值小于key，说明key在右边，
                // 因此将left移到mid+1的位置
                left=mid+1;
            }else{
                return mid;//如果mid值就是key，直接返回mid；
            }
        }
        return -1;//如果while循环走完还是没有找到key，说明数组中没有key；返回-1；
    }

    public static void main16(String[] args) {
        int[] array={1,3,6,9,12};//定义数组
        Scanner scan=new Scanner(System.in);
        int a=scan.nextInt();//从键盘输入数据
        int b=binarySearch(array,a);//调用并且接收返回的值
        System.out.println(b);
    }
    /*
    求数组中的平均值
     */
    public static double avg(int[] array2){
        double sum=array2[0];//先把array【0】的值给sum；
        double x= array2.length;//定义x为数组长度
        for(int i=1;i< array2.length;i++){//for循环从1开始遍历数组
            sum+=array2[i];//计算数组中每个值的和
        }
        return sum/x;//返回求平均值
    }

    public static void main15(String[] args) {
        int[] array={-1,2,3,4,5,6};
        System.out.println(avg(array));//调用并且接收平均值
    }
    /*
    找数组中的最大值
     */
    public static int max(int[] array1){
        if(array1==null||array1.length==0){
            return -1;
        }
        int max1=array1[0];//首先将max1中存放数组中第一个值，即array[0]
        for(int i=1;i< array1.length;i++){//再从下标为1开始遍历整个数组
            if(array1[i]>max1){//如果array【i】的值大于max就将max中的值替换掉
                max1=array1[i];
            }
        }
        return max1;//返回max1
    }
    public static void main14(String[] args) {
        int[] array={4,6,3,4,2};
        System.out.println( max(array));
    }


    public static void main13(String[] args) {
        int[] array={1,2,3,4,5};
        int[] ret=array.clone();//clone方法,产生需要克隆对象的副本
        System.out.println(Arrays.toString(ret));
    }
    public static void main12(String[] args) {
        int[] array={1,2,3,4,5};//定义一个array数组
        int[] ret=new int[array.length];//定义一个新的数组ret，长度为array的长度
        System.arraycopy(array,0,ret,0,array.length-4);
        System.out.println(Arrays.toString(ret));//src:源数组；
        // srcPos：源数组的pos位置开始拷贝；dest：拷贝到的目的数组；
        // destPos：拷贝拷贝到的目的数组的pos位置；length：拷贝多长
    }
    public static void main11(String[] args) {
        int[] array={1,2,3,4,5};
        int[] ret=Arrays.copyOf(array,array.length-4);//数组拷贝方式；
        // 拷贝的数组，拷贝的长度
        System.out.println(Arrays.toString(ret));
    }
    /*
    数组拷贝
     */
    public static void main10(String[] args) {
        int[] array={1,2,3,4,5};//定义一个数组
        int[] array2=new int[array.length];//定义一个新的数组array2，
        // 在堆里面开辟一个新的空间
        System.out.println(Arrays.toString(array2));//打印array2此时
        // 结果应为[0,0,0,0]
        for(int i=0;i< array.length;i++){//for循环将array中的数据拷贝到array2
            array2[i]=array[i];
        }
        System.out.println(Arrays.toString(array2));//再次打印array2
    }
   /*
   自己版本的数组转字符串
    */
    public static String myString(int[] array1) {//参数的判断是必不可少的
        if(array1==null){//如果数组为空引用，返回null；
            return null;
        }
        if(array1.length==0){//如果数组中什么都没有，返回“【】”
            return "[]";
        }
        String ret="[";//字符串首先为[
        for(int i=0;i<array1.length;i++) {//for循环遍历整个数组
            if(i!= array1.length-1){//如果i的值不为array1.length-1，
                // 证明不是数组中最后一个数
                ret=ret+array1[i]+", ";//ret的值就为array1[i]+","
            }else{//否则是数组最后一个数
                ret=ret+array1[i]+"]";//ret的值就为当前ret+array1[最后一个]+“]”
            }
        }
        return ret;//返回ret
    }
    public static void main9(String[] args) {
        int[] array={};
        //System.out.println(Arrays.toString(array));//返回一个字符串"[1,2,3]"
        String ret=myString(array);
        System.out.println(ret);
    }

    /*
    交换数组两个值
     */
    public static void swap(int[] array2){
        int tmp=array2[0];//把零号下标给tmp
        array2[0]=array2[1];//把1号下标放在0号位置；
        array2[1]=tmp;//再把tmp给1号下标
    }
    public static void main8(String[] args) {
        int[] array={10,20};
        swap(array);//调用swap方法
        System.out.print(Arrays.toString(array));//由于swap没有返回值，
        // 所以不用定义变量来接收它
    }
    /*
    青蛙跳台阶，循环方式
     */
    public static int jump(int n){
        int f1=1;
        int f2=2;
        int f3=0;
        for(int i=3;i<=n;i++){
            f3=f1+f2;
            f1=f2;
            f2=f3;
        }
        return f3;//返回你想得到的结果
    }
    public static void main7(String[] args) {
        System.out.println(jump(6));
    }
    /*
    青蛙跳台阶，一次可以跳一阶，也可以跳两阶
    问题：递归的效率很慢，有重复计算
    迭代实现：改为循环；
     */
    public static int fun1(int n){
        if(n<0){
            return -1;
        }
        if(n==1){//n代表当前有几个台阶
            return 1;
        }
        if(n==2){//n=2返回2
            return 2;
        }
        return fun1(n-1)+fun1(n-2);//跳台阶思想,例如四个台阶时，
        // 第一次选择跳一阶，那么剩余三阶就是三阶时的跳法；第一次选择跳两阶，
        // 那么剩余两阶就是两阶时的跳法
    }
    public static void main6(String[] args) {
        int i=4;
        System.out.println(fun1(i));
    }
    /*
    写一个方法，将数组中的每个元素都*2
     */
    public static int[] fun(int[] array3){//cheng方法用来给数组中每个数*2
        for(int i=0;i< array3.length;i++){//for循环遍历数组
            array3[i]=array3[i]*2;//将数组每个数*2，array中的值被改变
        }
        return array3;
    }
    public static int[] bux(int[] array4){//走完int[] array={1,2,3}调用，
        // 将array的地址给了array4，所以array和array4指向相同的变量
        int[] tmp=new int[array4.length];//开辟一个新的变量tmp
        for(int i=0;i< array4.length;i++){
            tmp[i]=array4[i]*2;//tmp是一个新的空间，有新的地址，它的值
            // 根据array4[i]*2改变，所以只改变了tmp的值，没有改变array中的值
        }
        return tmp;
    }
    public static void main5(String[] args) {
        int[] array={1,2,3};//定义数组中内容
        bux(array);//调用
        int[] array7=bux(array);//由于bux有返回值，所以定义array7接收返回值
        //System.out.println(Arrays.toString(fun(array)));
        System.out.println(Arrays.toString(array7));
        System.out.println(Arrays.toString(array));
    }
    /*
    两个引用同时指向一个对象
     */
    public static void print(int [] array2){//print方法用for循环遍历数组
        array2[0]=9999;//修改了数组下标为0的值
        for(int i=0;i< array2.length;i++){
            System.out.print(array2[i]+" ");//打印for循环遍历的数组结果
        }
    }//通过array2，来访问对象

    public static void main4(String[] args) {
        int[] array={1,2,3,4,5};//初始化数组
        print(array);//调用print
        for(int i=0;i< array.length;i++){
            System.out.print(array[i]+" ");
        }
    }
    /*
    数组遍历
     */
    public static void main3(String[] args) {
        int[] array={1,2,3,4};//静态初始化数组
        for(int i=0;i< array.length;i++){//使用for循环遍历数组
            System.out.print(array[i]+" ");
        }
        System.out.println();
        for(int x: array){//使用 for-each 遍历数组
            System.out.print(x+" ");
        }
        System.out.println();

        String str= Arrays.toString(array);
        System.out.println(str);//打印数组，
        // 打印方式：将数组以字符串形式输出
        //array=null;
        //System.out.println(array.length);//null.length
    }
    /*
    初始化数组
     */
    public static void main2(String[] args) {
        int[] array=new int[4];
        int[] array1=new int[]{1,2,3,4};
    }
    /*
    求斐波那契数列的第n项
     */
    public static int fib(int n) {//递归求fib思想：趋于终止的条件是
        // 如果第一项或者第二项为1，返回1；否则返回fib(n-1)+fib(n-2)
        if (n == 1 || n == 2) {
            return 1;
        }
        return fib(n-1)+fib(n-2);//自己调用自己
    }

    public static void main(String[] args) {
        int c=fib(8);
        System.out.println(c);//调用fib n=8；并且接收返回
    }
}